package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class MinimumSizeSubarraySum {
    // 2022-08-20 15:46:12
    /**
     * >= target 坑死
     *
     * 马上下播
     *
     * 周末不定时直播
     * 工作日 每天中午 12：30-13：30 直播刷题
     *
     *
     *
     *
     * 题解发布到 掘金 一条coding
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            // 练习 前缀和 + 二分 （双指针也可）
            int ans = Integer.MAX_VALUE;
            if (nums.length == 0) return 0;
            // 构建 前缀和 单调递增
            int[] sum = new int[nums.length + 1];
            for (int i = 1; i < sum.length; i++) {
                sum[i] = nums[i - 1] + sum[i - 1];
            }

            for (int i = 0; i < sum.length; i++) {
                int s = sum[i];
                // 在前缀和数组 二分查找
                int left = 0, right = i;
                while (left < right) {
                    int mid = (left + right + 1) / 2;
                    if (sum[mid] <= s - target) {
                        left = mid;
                    } else {
                        right = mid - 1;
                    }
                }
                if (sum[right] <= s - target) {
                    ans = Math.min(ans, i - right);
                }
            }
            return ans == Integer.MAX_VALUE ? 0 : ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}